package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author Fengkai
 * @creat 2023/4/18
 * 给定一个正整型数组表示待系统执行的任务列表，
 * 数组的每一个元素代表一个任务，元素的值表示该任务的类型。
 * 请计算执行完所有任务所需的最短时间。
 * 任务执行规则如下:
 * 任务可以按任意顺序执行，且每个任务执行耗时间均为 1 个时间单位。
 * 两个同类型的任务之间必须有长度为 N 个单位的冷却时间，
 * 比如:N 为 2 时，在时间 K 执行了类型 3 的任务，
 * 那么K+1 和 K+2 两个时间不能执行类型 3 任务。
 * 系统在任何一个单位时间内都可以执行一个任务，或者等待状态。
 * 说明:数组最大长度为 1000 数组最大值 1000。
 * 输入
 * 第一行记录一个用 半角逗号 分隔的数组，
 * 数组长度不超过 1000，数组元素的值不超过 1000
 * 第二行记录任务冷却时间，N 为正整数，N <= 100。
 * 输出
 * 输出为执行完所有任务所需的最短时间。
 */
public class MinCostTime {
    public static void main (String[] args) {
        System.out.println(minCostTime(new int[]{1, 2, 4, 3}, 2));
    }

    public static int minCostTime (int[] tasks, int cd) {
        //键为任务类型  栈的大小为任务数量
        HashMap<Integer, Stack<Integer>> typeCount = new HashMap<>();
        //记录每个任务的cd时间
        HashMap<Integer, Integer> cdMap = new HashMap<>();
        for (int task : tasks) {
            Stack<Integer> orDefault = typeCount.getOrDefault(task, new Stack<Integer>());
            orDefault.push(0);
            typeCount.put(task, orDefault);
            cdMap.put(task, cdMap.getOrDefault(task, 0));
        }
        int cost = 0;
        while (typeCount.size() > 0) {
            int index = -1;
            for (Map.Entry<Integer, Stack<Integer>> integerStackEntry : typeCount.entrySet()) {
                Integer key = integerStackEntry.getKey();
                if (cdMap.get(key) == 0) {
                    Stack<Integer> stack = typeCount.get(key);
                    stack.pop(); //执行key类型任务
                    if (stack.size() == 0) {
                        typeCount.remove(key);
                    }
                    cdMap.put(key, cd);
                    index = key;
                    break;
                }
            }
            //除了当前执行的任务  所有类型cd -1
            for (Integer integer : cdMap.keySet()) {
                if (integer != index) {
                    cdMap.put(integer, Math.max(cdMap.get(integer) - 1, 0));
                }
            }
            index = -1;
            cost++;
        }
        return cost;
    }

}
